﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace compresor2
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var lect = Console.ReadLine().Split();
            Console.WriteLine(Directory.GetCurrentDirectory() + "/" + lect[1]);
            if (!File.Exists(Directory.GetCurrentDirectory() + "/" + lect[1]))
            {
                Console.WriteLine("No se encuentra el archivo");
                Console.ReadKey();
                return;
            }
            byte[] bytearray = File.ReadAllBytes(Directory.GetCurrentDirectory() + "/" + lect[1]);
            Shannon s = new Shannon(bytearray);
            if (lect[0].ToLower() == "c")
            {
                s.comprimir();
            }
            else if (lect[0].ToLower() == "d")
            {
                s.descomprimir();
            }
            else
            {
                Console.WriteLine("Los comandos son: c o d");
                Console.ReadKey();
                return;
            }
            Console.ReadKey();
        }

    }
    public class Arbol
    {
        public class Nodo
        {
            public Nodo Derecho
            {
                get;
                set;
            }
            public Nodo Izquierdo
            {
                get;
                set;
            }
            public byte Symbol
            {
                get;
                set;
            }
            public Nodo()
            {
                Izquierdo = null;
                Derecho = null;
                Symbol = new byte();
            }
            public Nodo(Nodo d, Nodo i)
            {
                Derecho = d;
                Izquierdo = i;
                Symbol = new byte();
            }
        }

        public Nodo Raiz
        {
            get;
            set;
        }
        public Arbol()
        {
            Raiz = new Nodo(null, null);
            Current = Raiz;
        }

        public Nodo Current { get; set; }

        internal void MoveNext(int bit)
        {
            if (bit == 0)
                Current = Current.Izquierdo;
            else
                Current = Current.Derecho;

        }

        internal void Reset()
        {
            Current = Raiz;
        }

        internal bool EsHoja(Nodo p)
        {
            if (p.Izquierdo == null && p.Derecho == null)
                return true;
            else
                return false;
        }
    }
    public class Shannon
    {
        private byte[] bytesoriginales;
        public struct symbolValue
        {
            /// <summary>
            /// No literalmente se usa para frecuencia y frecuencia acumulada
            /// </summary>
            public double frecuencia;
            public double frecuenciaLog;
            public bitStream codigo;
            public symbolValue(double f)
            {
                frecuencia = f;
                codigo = null;
                frecuenciaLog = 0;
            }
            public symbolValue(double f, double g)
            {
                frecuencia = f;
                codigo = null;
                frecuenciaLog = g;
            }
            public symbolValue(double f, double g, bitStream h)
            {
                frecuencia = f;
                codigo = new bitStream();
                foreach (var x in h.ReadOne())
                {
                    codigo.Write(x);
                }

                frecuenciaLog = g;
            }
            public override string ToString()
            {
                return string.Format("{0},{1}", frecuencia, codigo.ToString());
            }
        }
        public int total { get; set; }
        public Dictionary<byte, symbolValue> symbols { get; set; }
        public Shannon(Byte[] bytearray)
        {
            this.bytesoriginales = bytearray;
        }

        public bitStream nuevocodigo { get; set; }

        internal void comprimir()
        {
            #region Calcular Pi
            //Calculamos las frecuencias de aparicion de cada simbolo diferente

            symbols = new Dictionary<byte, symbolValue>();
            foreach (var byt3 in bytesoriginales)
            {
                symbolValue lastFrecuency;
                if (symbols.TryGetValue(byt3, out lastFrecuency))
                {
                    symbols[byt3] = new symbolValue(++(lastFrecuency.frecuencia));
                }
                else
                {
                    symbols.Add(byt3, new symbolValue(1));
                }
            }

            #endregion
            #region Calcular Li
            var query = (from sym in symbols
                         let fr = (sym.Value.frecuencia / bytesoriginales.Length)
                         orderby fr descending
                         select new { sym, fr }).ToList();
            //Determino los Li
            List<int> Li = new List<int>();
            for (int i = 0; i < symbols.Count; i++)
            {
                var symbol = query[i];
                // Log2 1/pi donde pi = frecuencia/total
                var aux = Math.Log(1 / (symbol.fr), 2);
                symbols[symbol.sym.Key] = new symbolValue(symbol.sym.Value.frecuencia, aux);
                if ((aux + 1) % 1 == 0)
                {
                    Li.Add((int)aux);
                }
                else
                {
                    Li.Add((int)(aux + 1));
                }
            }
            #endregion
            #region Frecuencias acumuladas
            //Paso de frecuencias acumuladas de los pi de decimal a binario
            List<double> FA = new List<double>();
            double acum = 0;
            FA.Add(acum);
            foreach (var p in query)
            {
                acum += p.fr;
                FA.Add(acum);
            }
            FA.RemoveAt(FA.Count - 1);
            var maximalong = Li.Max();
            List<bitStream> fraccionalbinarios = new List<bitStream>();
            int itLI = 0;
            var primerbitstream = new bitStream();
            while (itLI < Li[0])
            {
                primerbitstream.Write(0);
                itLI++;
            }
            fraccionalbinarios.Add(primerbitstream);
            for (int i = 1; i < symbols.Count; i++)
            {
                bitStream bs = new bitStream();
                BinaryHelper.FractionDecToBin(FA[i], bs, maximalong - 1);
                fraccionalbinarios.Add(bs);
            }
            #endregion
            #region CODIFICACION
            //Tomar de la parte fraccionaria de los numeros binarios Li cifras
            for (int i = 0; i < symbols.Count; i++)
            {
                var aux = query[i];
                bitStream bits = new bitStream();
                int it = 0;
                if(aux.sym.Key == 97)
                    i = i + 1 - 1;
                foreach (var a in fraccionalbinarios[i].ReadOne())
                {
                    if (it < Li[i])
                    {
                        bits.Write(a);
                        it++;
                    }
                    else
                        break;
                }
                symbols[aux.sym.Key] = new symbolValue(aux.sym.Value.frecuencia, aux.sym.Value.frecuenciaLog, bits);
            }
            //Encabezado 
            //Extension
            //Cantidad de bytes
            nuevocodigo = new bitStream();
            var cantbytecount = nuevocodigo.cant_bits(bytesoriginales.Length);
            for (int i = 0; i < 32 - cantbytecount; i++)
            {
                nuevocodigo.Write(0);
            }
            nuevocodigo.Write(bytesoriginales.Length);
            //Cantidad de simbolos distintos
            var cantsymbolcount = nuevocodigo.cant_bits(symbols.Count - 1);
            for (int i = 0; i < 8 - cantsymbolcount; i++)
            {
                nuevocodigo.Write(0);
            }
            nuevocodigo.Write(symbols.Count - 1);
            //terna codigo de simbolo, longitud, nuevo codigo
            foreach (var x in symbols)
            {
                cantsymbolcount = nuevocodigo.cant_bits(x.Key);
                for (int i = 0; i < 8 - cantsymbolcount; i++)
                {
                    nuevocodigo.Write(0);
                }
                nuevocodigo.Write(x.Key);
                var f = 5 - nuevocodigo.cant_bits(x.Value.codigo.Total);
                while (f > 0)
                {
                    nuevocodigo.Write(0);
                    f--;
                }
                nuevocodigo.Write(x.Value.codigo.Total);
                foreach (var bit in x.Value.codigo.ReadOne())
                {
                    nuevocodigo.Write(bit);
                }
            }
            foreach (var byt3_ in bytesoriginales)
            {
                var aux = symbols[byt3_];
                foreach (var bit in aux.codigo.ReadOne())
                {
                    nuevocodigo.Write(bit);
                }
            }
            #endregion
            if (!File.Exists(Directory.GetCurrentDirectory() + "/comprimido.facu"))
            {
                File.Create(Directory.GetCurrentDirectory() + "/comprimido.facu");
            }
            
            File.WriteAllBytes(Directory.GetCurrentDirectory() + "/comprimido.facu", nuevocodigo.Bytes.ToArray());
        }
        enum Status
        {
            original,
            longitud,
            nuevo,
            datos
        }
        internal void descomprimir()
        {
            Arbol _Arbol = new Arbol();
            bitStream bits = new bitStream();
            int TotalDeSimbolos = bytesoriginales[3] << 0 | bytesoriginales[2] << 8 | bytesoriginales[1] << 16 | bytesoriginales[0] << 24;

            int simbolosDistintos = bytesoriginales[4];
            simbolosDistintos++;
            bytesoriginales = bytesoriginales.SubArray(5, bytesoriginales.Length - 5);
            bits.Bytes = bytesoriginales.ToList();
            int i = 7;
            List<byte> ListaCodigos = new List<byte>();
            List<bitStream> ListaCodigosNuevos = new List<bitStream>();
            List<byte> Descomprimido = new List<byte>();
            bitStream aux = new bitStream();
            Status estado = new Status();
            estado = Status.original;
            int codigo = 0;
            int longitud = 0;
            foreach (var bit in bits.ReadOne())
            {
                switch (estado)
                {
                    case Status.original:
                        if (bit == 1)
                            codigo += (int)Math.Pow(2, i);
                        i--;
                        if (i == -1)
                        {
                            ListaCodigos.Add((byte)codigo);
                            estado = Status.longitud;
                            codigo = 0;
                            i = 4;
                            break;
                        }
                        break;
                    case Status.longitud:
                        if (bit == 1)
                            longitud += (int)Math.Pow(2, i);
                        i--;
                        if (i == -1)
                        {
                            estado = Status.nuevo;
                            i = 7;
                        }
                        break;
                    case Status.nuevo:
                        aux.Write(bit);
                        longitud--;
                        if (longitud == 0)
                        {
                            simbolosDistintos--;
                            longitud = 0;
                            ListaCodigosNuevos.Add(new bitStream(aux));
                            aux = new bitStream();
                            if (simbolosDistintos == 0)
                            {
                                int j = 0;
                                foreach (var simbolos in ListaCodigosNuevos)
                                {
                                    cargarArbol(ListaCodigos[j], simbolos.ReadOne().ToList(), _Arbol.Raiz);
                                    j++;
                                }
                                estado = Status.datos;
                                i = 0;
                            }
                            else
                            {
                                estado = Status.original;
                            }
                        }
                        break;
                    case Status.datos:
                        _Arbol.MoveNext(bit);
                        if (_Arbol.EsHoja(_Arbol.Current))
                        {
                            i++;
                            Descomprimido.Add(_Arbol.Current.Symbol);
                            _Arbol.Reset();
                            if (i > TotalDeSimbolos - 1)
                            {
                                i = i + 1 - 1;
                                FileStream descomp = File.Create(Directory.GetCurrentDirectory() + "/miarchivo.txt");
                                descomp.Write(Descomprimido.ToArray(), 0, TotalDeSimbolos - 1);
                                return;
                            }
                        }
                        break;
                }

            }
        }

        private void cargarArbol(byte symbol, List<int> simbolos, Arbol.Nodo Raiz)
        {
            if (simbolos.Count == 0)
                return;
            if (simbolos[0] == 0)
            {
                if (Raiz.Izquierdo == null)
                {
                    Raiz.Izquierdo = new Arbol.Nodo(null, null);
                    if (simbolos.Count != 1)
                    {
                        cargarArbol(symbol, simbolos.GetRange(1, simbolos.Count - 1), Raiz.Izquierdo);
                    }
                    else
                    {
                        Raiz.Izquierdo.Symbol = symbol;
                    }
                }
                else
                {
                    cargarArbol(symbol, simbolos.GetRange(1, simbolos.Count - 1), Raiz.Izquierdo);
                }
            }
            else
            {
                if (Raiz.Derecho == null)
                {
                    Raiz.Derecho = new Arbol.Nodo(null, null);
                    if (simbolos.Count != 1)
                    {
                        cargarArbol(symbol, simbolos.GetRange(1, simbolos.Count - 1), Raiz.Derecho);
                    }
                    else
                    {
                        Raiz.Derecho.Symbol = symbol;
                    }
                }
                else
                {
                    cargarArbol(symbol, simbolos.GetRange(1, simbolos.Count - 1), Raiz.Derecho);
                }
            }
        }


    }
    public class bitStream
    {
        List<Byte> Memory;

        public List<Byte> Bytes
        {
            get { return Memory; }
            set
            {
                total = value.Count * 8;
                Memory = value;
            }
        }
        int total;

        public int Total
        {
            get { return total; }
            set { total = value; }
        }
        public override string ToString()
        {
            string myString = "";
            int i = 0;
            foreach (var x in Memory)
            {
                myString += byteToBitsString(x);
                if (i > 5)
                    break;
                i++;
            }
            return string.Format("{0} Total {1}", myString, total);
        }
        private string byteToBitsString(byte byteIn)
        {
            var bitsString = new StringBuilder(8);

            bitsString.Append(Convert.ToString((byteIn / 128) % 2));
            bitsString.Append(Convert.ToString((byteIn / 64) % 2));
            bitsString.Append(Convert.ToString((byteIn / 32) % 2));
            bitsString.Append(Convert.ToString((byteIn / 16) % 2));
            bitsString.Append(Convert.ToString((byteIn / 8) % 2));
            bitsString.Append(Convert.ToString((byteIn / 4) % 2));
            bitsString.Append(Convert.ToString((byteIn / 2) % 2));
            bitsString.Append(Convert.ToString((byteIn / 1) % 2));

            return bitsString.ToString();
        }
        public bitStream()
        {
            total = 0;
            Memory = new List<Byte>();
        }
        public bitStream(bitStream a)
        {
            total = a.total;
            Memory = new List<Byte>();
            Memory = a.Memory.GetRange(0, a.Memory.Count);
        }
        public int cant_bits(int n)
        {
            if (n != 0)
            {
                int i = 0;
                uint count = 0;
                while (n != 0)
                {
                    i++;
                    count += (uint)n & 1;
                    n >>= 1;
                }
                return i;
            }
            else
                return 1;
        }
        /// <summary>
        /// Lee de a 1 bit se puede usar en foreach
        /// </summary>
        /// <returns>un int: 1 o 0</returns>
        public IEnumerable<int> ReadOne()
        {
            int i = 0;
            while (i < total)
            {
                int actual = (int)(byte)(Memory[(int)Math.Ceiling((double)(i / 8))] & pow2[i % 8]);
                if (actual != 0)
                {
                    yield return 1;
                }
                else
                {
                    yield return 0;
                }
                i++;
            }
        }
        int[] pow2 = { 128, 64, 32, 16, 8, 4, 2, 1 };


        /// <summary>
        /// No usar
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        [Obsolete]
        public int Read(int start, int end)
        {
            int end2 = end + start;
            int number = 0;
            int pos = end2 % 8;
            byte aux = new byte();
            int byte_ = (int)Math.Ceiling((double)(end2 / 8));
            int end3 = end2 - 1;
            if (end2 % 8 != 0)
            {
                while (end2 >= (start + end) - ((start + end) % 8))
                {
                    int actual = (int)(byte)(Memory[(int)Math.Ceiling((double)(end2 / 8))] & pow2[end3 % 8]);
                    if (actual != 0)
                    {
                        aux |= (byte)(1 << pos);
                    }
                    pos--;
                    end2--;
                    end3++;
                    if (end2 == start)
                    {
                        return number |= aux >> 8 - ((end + start) % 8) - 1;
                    }
                }
                number |= aux >> 8 - ((end + start) % 8) - 1;
                aux = new byte();
            }
            pos = end2 % 8;
            while (end2 >= start)
            {
                int actual = (int)(byte)(Memory[(int)Math.Ceiling((double)(end2 / 8))] & pow2[end2 % 8]);
                if (actual != 0)
                {
                    aux |= (byte)(1 << pos);
                }
                pos--;
                if (pos == 0)
                {
                    number |= aux << (byte_ * 8);
                    byte_--;
                    aux = new byte();
                    pos = 7;
                }
                end2--;
                if (end2 == start)
                {
                    return number |= (aux << 8 - (start % 8)) << (byte_ * 8);
                }
            }
            //if (pos < 8)
            //{
            // number |= (aux << pow2[byte_]) << (8 - pos);
            //}
            return number;
        }
        public void Write(int bits)
        {
            int count = cant_bits(bits);
            // casos posibles:
            // 1. total%8==0 tenemos todos los byte llenos y count=8 necesitamos 1 byte entero |\
            // 2. ( o no tenemos nada) y count<8 necesitamos 1 byte mas, no completo. |_|> En los 2 casos necesitamos 1 byte mas
            // 3. y count>8 necesitamos 1 o mas bytes.
            // 4. total%8!=0 nos sobra espacio sino si ((8-total)%8)>count estamos sobrados |\
            // 5. sino si ((8-total)%8)==count estamos justos |_|> En los 2 casos no necesitamos nada.
            // 6. sino si ((8-total)%8)<count nos falta 1 o mas bytes
            //
            // Ejemplo bits = 5 Osea 101 en binario y count = 3
            // y el buffer en: Memory 1010101 vamos por la opcion total%8 = 1 y 1 < 5 nos falta 1 o mas. (particularmente 1)
            if (total % 8 == 0)
            {
                Byte New;
                if (count == 8)
                {
                    New = new byte();

                    New = (byte)(bits);

                    Memory.Add(New);
                }
                else if (count < 8)
                {
                    New = new byte();
                    // ejemplo 12 ocupa 4 bits 1100 lo movemos al principio el byte 11000000
                    // asi en la despues de la posicion Total osea 4 desde ahora colocamos lo siguiente
                    New = (byte)(bits << (8 - count));
                    Memory.Add(New);
                }
                else
                {
                    // ejemplo 88552 10101100111101000 tiene 17 bits debemos colocarlos al principio de un nuevo byte
                    // cantidad de bytes RedondeoHaciaArriba(17/8)=3 y Resto = 17 mod 8 = 1 bit que van a parar al proximo byte
                    int Resto = count % 8;
                    int cantidadBytes = (int)Math.Ceiling((double)(count / 8));
                    // Desde el ultimo byte hasta el segundo
                    for (int i = cantidadBytes - 1; i > 0; i--)
                    {
                        New = new Byte();
                        New = (byte)(bits >> (8 * i + Resto));

                        Memory.Add(New);
                    }
                    New = new Byte();
                    New = (byte)(bits << (8 - Resto));
                    Memory.Add(New);
                }
            }
            else
            {
                // Total : 6
                // Memory:10000000
                // bits: 1111111 
                // Result => Memory: 10101011
                if ((8 - (total % 8)) == count)
                {
                    Memory[(int)Math.Round((double)(total / 8))] |= (byte)(bits);
                }
                // Total : 6
                // Memory:10000000
                // bits: 111(7)
                // Result => Memory: 10101011
                else if ((8 - (total % 8)) > count)
                {
                    Memory[(int)(total / 8)] |= (byte)(bits << ((8 - ((total) % 8)) - count));
                }
                else
                {
                    // 00011101 10110111 10110111 bits count 21
                    // 00011101 10110111 bits count 13
                    // 10101110 11110000 memory total 12
                    // result 10101110 11111110 11011011 10000000 memory total 25
                    // Resto 4 = (8 - (12%8)) Ultimos bits sobrantes
                    // RestoFinal 1 = 13 - 4 % 8
                    int Resto = 8 - (total % 8);
                    int RestoFinal;
                    RestoFinal = (count - Resto) % 8;

                    Memory[(int)Math.Round((double)(total / 8))] |= (byte)(bits >> (count - Resto));
                    int cantidadBytes;
                    byte New;
                    if (RestoFinal == 0)
                        cantidadBytes = (int)Math.Ceiling((double)((double)(count - Resto) / 8)) + 1;
                    else
                        cantidadBytes = (int)Math.Ceiling((double)((double)(count - Resto) / 8));
                    for (int i = cantidadBytes - 1; i > 0; i--)
                    {
                        New = new Byte();
                        New = (byte)(bits >> (8 * (i - 1) + RestoFinal));
                        Memory.Add(New);
                    }
                    if (RestoFinal > 0)
                    {
                        New = new Byte();
                        New = (byte)(bits << 8 - RestoFinal);
                        Memory.Add(New);
                    }
                }
            }
            total = (count + total);

        }
    }
    /// <summary>
    /// Clase de utileria
    /// </summary>
    public static class BinaryHelper
    {
        public static T[] SubArray<T>(this T[] data, int index, int length)
        {
            T[] result = new T[length];
            Array.Copy(data, index, result, 0, length);
            return result;
        }

        internal static void FractionDecToBin(double fa, bitStream bs, int i)
        {
            if (i == -1)
                return;
            var valor = fa - (int)fa; // parte decimal. ej: 1,14 - 1 = 0,14
            //if (fa == 0)
            // return;
            var valor2 = (int)(valor * 2); // multiplicamos por 2 y sacamos la parte entera 
            bs.Write(valor2);
            FractionDecToBin(valor * 2, bs, i - 1);
        }
    }
}
 